# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：n = 3
# 输出：["((()))","(()())","(())()","()(())","()()()"]
#  
# 
#  示例 2： 
# 
#  
# 输入：n = 1
# 输出：["()"]
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= n <= 8 
#  
# 
#  Related Topics 字符串 动态规划 回溯 👍 3731 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [set() for _ in range(n + 1)]
        dp[0]={''}
        for i in range(1,n+1):
            for k in range(i):
                # （左边）右边的形式，因为已经消耗了一个括号，所以k取[0,i-1).对于每一个可以取的k值，如果左边有k个，那么右边就一定有(i-1) -k个
                for left in dp[k]:
                    for right in dp[i-1-k]:
                        dp[i].add(f'({left}){right}')
        return list(dp[n])
# leetcode submit region end(Prohibit modification and deletion)
